package com.c2b.algorithm.leetcode.base;

import java.util.Stack;

/**
 * <a href="https://leetcode.cn/problems/minimum-distance-between-bst-nodes/">二叉搜索树节点最小距离(Minimum Distance Between BST Nodes)</a>
 * <p>给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。
 * <p>
 * 差值是一个正数，其数值等于两值之差的绝对值。</p>
 *
 * <pre>
 * 示例 1：
 *      输入：root = [4,2,6,1,3]
 *                  4
 *                 / \
 *                2   6
 *               / \
 *              1   3
 *      输出：1
 *
 * 示例 2：
 *      输入：root = [1,0,48,null,null,12,49]
 *                  1
 *                 / \
 *                0   48
 *                   / \
 *                 12   49
 *      输出：1
 * </pre>
 * <b>提示：</b>
 * <ul>
 *     <li>树中节点的数目范围是 [2, 100]</li>
 *     <li>0 <= Node.val <= 10^5</li>
 * </ul>
 *
 * @author c2b
 * @since 2023/5/25 9:34
 */
public class LC0783MinDiffInBST_S {

    public int minDiffInBST(TreeNode root) {
        //minDiffInBSTByRecursion(root);
        minDiffInBSTByIteration(root);
        return minDistance;
    }

    int minDistance = Integer.MAX_VALUE;
    int lastVal = -1;

    public void minDiffInBSTByIteration(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        while (!stack.isEmpty() || root != null) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            if (lastVal != -1) {
                minDistance = Math.min(minDistance, root.val - lastVal);
                // 提前退出
                if (minDistance == 1) {
                    return;
                }
            }
            lastVal = root.val;
            root = root.right;
        }
    }

    public void minDiffInBSTByRecursion(TreeNode root) {
        if (root == null) {
            return;
        }
        minDiffInBSTByRecursion(root.left);
        if (lastVal != -1) {
            minDistance = Math.min(minDistance, root.val - lastVal);
            // 提前退出
            if (minDistance == 1) {
                return;
            }
        }
        lastVal = root.val;
        minDiffInBSTByRecursion(root.right);
    }

    public static void main(String[] args) {
        TreeNode left = new TreeNode(0);
        TreeNode right = new TreeNode(48, new TreeNode(12), new TreeNode(49));
        TreeNode root = new TreeNode(1, left, right);
        //TreeNode left = new TreeNode(2, new TreeNode(1), new TreeNode(3));
        //TreeNode right = new TreeNode(6);
        //TreeNode root = new TreeNode(3, left, right);
        //TreeNode root = new TreeNode(90);
        //root.left = new TreeNode(69);
        //root.left.left = new TreeNode(49);
        //root.left.right = new TreeNode(89);
        //root.left.left.right = new TreeNode(52);
        LC0783MinDiffInBST_S lc0783MinDiffInBST_s = new LC0783MinDiffInBST_S();
        System.out.println(lc0783MinDiffInBST_s.minDiffInBST(root));
    }
}
